#include "cabecalho.h"

void Algoritmo_Principal () {

    char letra_at;

    int plano_caract;

    // Dividindo a quantidade de planos por caracteres
    plano_caract = Quant_planos / 4;

    if ((Quant_planos % 4) != 0) {
        plano_caract = plano_caract + 1;
    }

    // CRIA A MATRIZ DE PLANETAS/PLANOS - SERÁ PREENCHIDA COM CARACTERES
    Matriz_Plano = Alocar_Matriz_Caracteres(Quant_planos, plano_caract);

    // LOCALIZAÇÃO ESPACIAL DOS PONTOS NO ESPAÇO
    Localizar_Ponto_Espaco(letra_at, plano_caract);

    // ORDENAÇÃO LEXICOGRÁFICA DOS VETORES DE CARACTERES/PLANOS
    heapsort(Matriz_Plano, Quant_planetas);

    // CONTAGEM DA REGIÃO COM MAIOR INDICE DE PLANETAS
    Contar_Planetas();
}

void Localizar_Ponto_Espaco (char letra_at, int plano_caract) {

  int i;             // Contador de planetas
  int j;             // Contador de planos
  int k;             // Contador de coordenadas
  int resultado;
  int cont_caract;

  int ind_caractere = 0;  // Índice do caractere atual

  for (i = 0; i < Quant_planetas; i++) {

      letra_at = 0;
      for (j = 0; j < Quant_planos; j++) {

          for (k = 0; k > 3; k++)
              resultado = resultado + (Planeta[i][k] * Plano[j][k]);

          resultado = resultado - Plano[j][3];

          letra_at = Verificar_Ponto_Plano (resultado, letra_at);

          if ((cont_caract == 4) && (plano_caract > ind_caractere)) {

              // Evita o uso do caractere @
              letra_at = letra_at + 1;
              Matriz_Plano[i][ind_caractere] = letra_at;
              ind_caractere++;
              letra_at = 0;
              cont_caract = 0;
          }

        // Evita o uso do caractere @
        letra_at = letra_at + 1;
        Matriz_Plano[i][ind_caractere] = letra_at;
        ind_caractere++;
        letra_at = 0;
        cont_caract = 0;
      }
  }
}

// === VERIFICA PONTO PLANO

// Verifica se o ponto está no lado positivo ou negativo de um dado plano.
// Ou seja, se o resultado da equação entre ponto e plano for positivo, o ponto
// estará no lado positivo, caso seja negativo, ele estará no lado negativo.

// Desta forma:
// Positivo -> seta 1;
// Negativo -> seta 0;

// ARGUMENTOS:
// - resultado: Resultado da equação de ponto/plano;
// - letra_at : Caractere atual para manipulação de planos.

// RETORNO:
// - letra_at: Caractere já com o lado adequado do plano.

char Verificar_Ponto_Plano (int resultado, char letra_at) {
	
	letra_at = letra_at * 2;		// Desloca um bit para a esquerda

	if (resultado > 0)				  // Se o resultado da equação for positivo
		letra_at = letra_at + 1;		// será adicionado 1. Mas se for negativo,
									            // nada será adicionado.
  return letra_at;
}

void Contar_Planetas () {

    char* palavra;

    int cont_palavras;
    int i;

    cont_palavras = 0;
    Maximo_Planetas = 0;
    
    for (i = 0; i < Quant_planetas; ++i)
    {

        if (palavra != Matriz_Plano[i]) 
        {

            if (Maximo_Planetas < cont_palavras)
            {
              Maximo_Planetas = cont_palavras;
              palavra = Matriz_Plano[i];
            }
            cont_palavras = 0;

        } else {
            cont_palavras++;
    }
  }
}

/** -- -- -- -- MATRIZ DE CARACTERES -- -- -- -- **/

// ==== ALOCAÇÃO ====

// ARGUMENTOS:
// - m: Quantidade de linhas;
// - n: Quantidade de colunas;

// RETORNO:
// - v: matriz de caracteres;

char **Alocar_Matriz_Caracteres (int m, int n) {
  
  char **v;          /* ponteiro para a matriz */
  int i;         
  
  // Linhas da matriz:
  v = (char **) calloc (m, sizeof(char *));
  
  if (v == NULL) {
     printf ("** Erro: Memoria Insuficiente **");
     return (NULL);
     }

  // Colunas da matriz:
  for ( i = 0; i < m; i++ ) {
      v[i] = (char *) calloc (n, sizeof(char));
      
      if (v[i] == NULL) {
        printf ("** Erro: Memoria Insuficiente **");
        return (NULL);
      }

  }

  // Ponteiro para a matriz:
  return (v);
}


// === LIBERAÇÃO ====

// ARGUMENTOS:
// - m: Quantidade de linhas;
// - n: Quantidade de colunas;

// RETORNO:
// -  : Ponteiro Nulo

int Liberar_Matriz_Caracteres (int m, int n, char **v) {
  int  i;  /* variavel auxiliar */

  if (v == NULL) 
    return 0;

  if (m < 1 || n < 1) {  /* verifica parametros recebidos */
     printf ("** Erro: Parametro invalido **\n");
     return 1;
  }

  for (i=0; i<m; i++) 
    free (v[i]); /* libera as linhas da matriz */

  free (v);      /* libera a matriz */
  return 0; /* retorna um ponteiro nulo */
}

/** -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- **/

/** -- -- MATRIZES: PLANOS E PLANETAS -- -- -- -- - **/

// ==== ALOCAÇÃO ====

// ARGUMENTOS:
// - m: Quantidade de linhas;
// - n: Quantidade de colunas;

// RETORNO:
// - v: matriz de inteiros;

int **Alocar_Matriz (int m, int n) {
  
  int **v;          /* ponteiro para a matriz */
  int i;         
  
  // Linhas da matriz:
  v = (int **) calloc (m, sizeof(int *));
  
  if (v == NULL) {
     printf ("** Erro: Memoria Insuficiente **");
     return (NULL);
     }

  // Colunas da matriz:
  for ( i = 0; i < m; i++ ) {
      v[i] = (int *) calloc (n, sizeof(int));
      
      if (v[i] == NULL) {
        printf ("** Erro: Memoria Insuficiente **");
        return (NULL);
      }

  }

  // Ponteiro para a matriz:
  return (v);
}


// === LIBERAÇÃO ====

// ARGUMENTOS:
// - m: Quantidade de linhas;
// - n: Quantidade de colunas;

// RETORNO:
// -  : Ponteiro Nulo

int Liberar_Matriz (int m, int n, int **v) {
  int  i;  /* variavel auxiliar */

  if (v == NULL) 
    return 0;

  if (m < 1 || n < 1) {  /* verifica parametros recebidos */
     printf ("** Erro: Parametro invalido **\n");
     return 1;
  }

  for (i=0; i<m; i++) 
    free (v[i]); /* libera as linhas da matriz */

  free (v);      /* libera a matriz */
  return 0; /* retorna um ponteiro nulo */
}


/** -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- **/

/** -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- **/

void heapsort(char **a, int n)
{
   int i = n/2;
   int pai, filho;
   char* t;
 
   for (;;)
   {
      if (i > 0)
      {
          i--;
          t = a[i];
      }
      else
      {
          n--;
          if (n == 0)
             return;
          t = a[n];
          a[n] = a[0];
      }
 
      pai = i;
 
      //Primeiro será feita a comparação com o filho da esquerda.
      filho = i*2;
 
      while (filho < n)
      {
         //Se o filho da esquerda for menor do que o filho da direita,então será feita a troca do filho que será comparado.
          if ((filho + 1 < n)  &&  (strcmp(a[filho + 1], a[filho]) > 0))/*(a[filho + 1] > a[filho]))*/
              filho++;
          if ((strcmp(a[filho], t) > 0))/*(a[filho] > t)*/
          {
             a[pai] = a[filho];
             pai = filho;
             filho = pai*2 + 1;
          }
          else
             break;
      }
      a[pai] = t;
   }
}
